Spot-On
spot-on-pacify.h
1 /*
2 ** Copyright (c) 2011 - 10^10^10, Mattias AndrĂ©e, Alexis Megas.
3 ** All rights reserved.
4 **
5 ** Redistribution and use in source and binary forms, with or without
6 ** modification, are permitted provided that the following conditions
7 ** are met:
8 ** 1. Redistributions of source code must retain the above copyright
9 ** notice, this list of conditions and the following disclaimer.
10 ** 2. Redistributions in binary form must reproduce the above copyright
11 ** notice, this list of conditions and the following disclaimer in the
12 ** documentation and/or other materials provided with the distribution.
13 ** 3. The name of the author may not be used to endorse or promote products
14 ** derived from Spot-On without specific prior written permission.
15 **
16 ** SPOT-ON IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
17 ** IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
18 ** OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
19 ** IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
20 ** INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
21 ** NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
22 ** DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
23 ** THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24 ** (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
25 ** SPOT-ON, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26 */
27 
28 #ifndef _spoton_pacify_h_
29 #define _spoton_pacify_h_
30 
31 #include <algorithm>
32 #include <cmath>
33 #include <map>
34 #include <string>
35 
37 {
38  public:
39  spoton_pacify(const std::string &passphrase)
40  {
41  size_t n = passphrase.length();
42 
43  // Convert from UTF-8 to UTF-32.
44  // Note this is not an attack-safe implementation,
45  // this implementation allows characters that are
46  // encoded with an excessive number of bytes.
47 
48  // Count the number of characters.
49  // Byte Datum
50  // 0....... Single-byte character (Count these.)
51  // 11...... Initial byte in multibyte character (Count these.)
52  // 10...... Non-initial byte in multibyte character (Do not count these.)
53 
54  m_passphrase = 0;
55  m_passphrase_length = 0;
56 
57  for(size_t i = 0; i < n; i++)
58  if((static_cast<int> (passphrase.at(i)) & 0xc0) != 0x80)
59  m_passphrase_length += 1;
60 
61  if(m_passphrase_length > 0)
62  m_passphrase = new long int[m_passphrase_length];
63 
64  // Convert.
65  // 0.......
66  // 110..... 10......
67  // 1110.... 10...... 10......
68  // 11110... 10...... 10...... 10......
69  // 111110.. 10...... 10...... 10...... 10......
70  // 1111110. 10...... 10...... 10...... 10...... 10......
71 
72  for(size_t i = 0, j = 0; i < n; j++)
73  {
74  int c = static_cast<int> (passphrase.at(i++));
75 
76  if((c & 0x80) == 0)
77  {
78  // Single-byte character.
79 
80  if(m_passphrase)
81  m_passphrase[j] = static_cast<long int> (c);
82  }
83  else if((c & 0xc0) == 0xc0)
84  {
85  // Initial byte in multibyte-character.
86 
87  int b = 0;
88 
89  // Get width of character.
90  // 110..... 2-byte character 11-bit character
91  // 1110.... 3-byte character 16-bit character
92  // 11110... 4-byte character 21-bit character (New UTF-8 Limit)
93  // 111110.. 5-byte character 26-bit character
94  // 1111110. 6-byte character 31-bit character (Old UTF-8 Limit)
95 
96  while(c & 0x80)
97  b++, c <<= 1;
98 
99  if(b > 6)
100  {
101  if(m_passphrase)
102  m_passphrase[j] = 0; /* XXX invalid input. */
103 
104  break;
105  }
106 
107  // Get bits (represented by dots in the table above)
108  // stored in the start byte.
109 
110  c = (c & 0xff) >> b;
111 
112  if(m_passphrase)
113  m_passphrase[j] = static_cast<long int> (c);
114 
115  // We have read one of the bytes.
116 
117  b--;
118 
119  // Get bits stored in the continuation bytes.
120  // 10......
121 
122  while(b--)
123  {
124  if(i == n)
125  {
126  // Premature end of string.
127 
128  if(m_passphrase)
129  m_passphrase[j] = 0; /* XXX invalid input. */
130 
131  break;
132  }
133 
134  c = static_cast<int> (passphrase.at(i++));
135 
136  if((c & 0xc0) != 0x80)
137  {
138  // Premature end of multibyte-character byte sequence.
139 
140  if(m_passphrase)
141  m_passphrase[j] = 0; /* XXX invalid input. */
142 
143  i--;
144  break;
145  }
146  else
147  {
148  // Store the six lowest bits.
149 
150  if(m_passphrase)
151  {
152  m_passphrase[j] <<= 6;
153  m_passphrase[j] |= static_cast<long int> (c & 0x3f);
154  }
155  }
156  }
157  }
158  else
159  // Non-initial byte in multibyte-character at beginning of character.
160  // (Unexpected continuation byte.)
161 
162  j--; /* XXX invalid input. */
163  }
164  }
165 
166  ~spoton_pacify()
167  {
168  delete []m_passphrase;
169  }
170 
171  double evaluate(void) const
172  {
173  if(!m_passphrase || m_passphrase_length == 0)
174  return 25.0; // Error!
175 
176  double rc = 0.0;
177  long int last = -1;
178  std::map<long int, int> used;
179  std::map<double, int> classes;
180 
181  classes[2.5] = 0;
182  classes[3.5] = 0;
183 
184  for(int i = 1; i <= 10; i++)
185  classes[i] = 0;
186 
187  for(size_t i = 0; i < m_passphrase_length; i++)
188  {
189  double r = 0.0;
190  long int c = m_passphrase ? m_passphrase[i] : 0;
191 
192  r = char_class(c);
193 
194  if(used.end() == used.find(c))
195  used[c] = 1;
196  else
197  used[c] += 1;
198 
199  rc += std::pow(r, 2);
200  rc += 5.0 / used[c];
201 
202  if(r >= 4.0)
203  r += 2.0;
204  else if(r > 3.0)
205  r = 5.0;
206  else if(r == 3.0)
207  r = 4.0;
208  else if(r > 2.0)
209  r = 3.0;
210 
211  if(classes.end() == classes.find(r - 1.0))
212  classes[r - 1.0] = 0;
213 
214  classes[r - 1.0] += 1;
215 
216  if(i > 0)
217  {
218  if(c > 127 || last > 127)
219  r = distance('\0', '\0');
220  else
221  r = distance(static_cast<char> (c), static_cast<char> (last));
222 
223  rc += std::pow(r, 0.5);
224  }
225 
226  last = c;
227  }
228 
229  if(rc >= 0.0)
230  rc += 30.0;
231 
232  double a = 0.0;
233  double b = 0.0;
234  double c = 0.0;
235  double d = 0.0;
236  int i = 0;
237 
238  for(std::map<double, int>::iterator it = classes.begin();
239  it != classes.end(); i++, it++)
240  if(i == 0)
241  a = it->second;
242  else if(i == 1)
243  b = it->second;
244  else if(i == 2)
245  c = it->second;
246  else if(i == 3)
247  d = it->second;
248  else
249  break;
250 
251  if(a + b + c + d == 0.0)
252  rc += 30.0;
253  else
254  {
255  double r = std::pow(a, 2) + std::pow(b, 2) + std::pow(c, 3) +
256  std::pow(d, 2);
257 
258  rc += 30.0 * static_cast<double> (m_passphrase_length) /
259  std::pow(r, 0.5);
260  }
261 
262  return std::floor(rc + 0.5);
263  }
264 
265  private:
266  long int *m_passphrase;
267  size_t m_passphrase_length;
268 
269  double char_class(const long int c) const
270  {
271  if(static_cast<long int> ('0') <= c && c <= static_cast<long int> ('9'))
272  return 1.0;
273  else if(static_cast<long int> ('a') <= c &&
274  c <= static_cast<long int> ('z'))
275  return 2.0;
276  else if(static_cast<long int> ('A') <= c &&
277  c <= static_cast<long int> ('Z'))
278  return 2.5;
279  else if(c < (1 << 7))
280  return 3.0;
281  else if(c < (1 << 8))
282  return 3.5;
283  else if(c < (1 << 10))
284  return 4.0;
285  else if(c < (1 << 14))
286  return 5.0;
287  else if(c < (1 << 16))
288  return 6.0;
289  else if(c < (1 << 18))
290  return 7.0;
291  else if(c < (1 << 22))
292  return 8.0;
293  else if(c < (1 << 26))
294  return 9.0;
295  else
296  return 10.0;
297  }
298 
299  double distance(const char a, const char b) const
300  {
301  std::string _a_;
302  std::string _b_;
303 
304  _a_.append(1, a);
305  _b_.append(1, b);
306  std::transform(_a_.begin(), _a_.end(), _a_.begin(), ::tolower);
307  std::transform(_b_.begin(), _b_.end(), _b_.begin(), ::tolower);
308 
309  if(_a_ == _b_)
310  return 0.0;
311 
312  std::map<char, std::pair<double, double> > keys;
313  std::string L1("1234567890");
314  std::string L2("qwertyuiop");
315  std::string L3("asdfghjkl");
316  std::string L4("zxcvbnm");
317  std::string _a_b_(_a_ + _b_);
318 
319  for(size_t i = 0; i < L1.length(); i++)
320  keys[L1[i]] = std::pair<double, double> (static_cast<double> (i), 0.0);
321 
322  for(size_t i = 0; i < L2.length(); i++)
323  keys[L2[i]] = std::pair<double, double> (static_cast<double> (i) + 0.5,
324  1.0);
325 
326  for(size_t i = 0; i < L3.length(); i++)
327  keys[L3[i]] = std::pair<double, double> (static_cast<double> (i) + 0.75,
328  2.0);
329 
330  for(size_t i = 0; i < L4.length(); i++)
331  keys[L4[i]] = std::pair<double, double> (static_cast<double> (i) + 1.0,
332  3.0);
333 
334  for(size_t i = 0; i < _a_b_.length(); i++)
335  if(keys.end() == keys.find(_a_b_[i]))
336  return 15.0;
337 
338  return std::pow(std::pow(keys[_a_.at(0)].first -
339  keys[_b_.at(0)].first, 2) +
340  std::pow(keys[_a_.at(0)].second -
341  keys[_b_.at(0)].second, 2), 0.5);
342  }
343 };
344 
345 #endif
Definition: spot-on-pacify.h:36